package org.example;

import java.util.*;

public class Stack1 {
    /*一：字符串转整数*/
    static class Basic {
        public static void main(String[] args) {
            String s = "458";
            int n = 0;
            for (int i = 0; i < s.length(); i++) {
                char c = s.charAt(i);
                // 这行代码是核心转换逻辑。c - '0' 用于将字符类型的数字转换为对应的整数。在 Java 里，字符类型本质上是整数，字符 '0' 到 '9' 的 ASCII 码是连续的，所以用字符减去 '0' 就能得到对应的整数值。例如，'4' - '0' 的结果是 4。
                // 10 * n 是为了将之前得到的部分结果左移一位，相当于乘以 10。例如，当第一次循环结束后 n 为 4，第二次循环时，10 * 4 得到 40，再加上当前字符转换后的整数（如 '5' - '0' 得到 5），就得到 45。
                // 循环结束后，n 就存储了字符串转换后的整数结果。
                // 有坑：(c - '0') 的这个括号不能省略，否则可能造成整型溢出。
                n = 10 * n + (c - '0');
            }
        }
    }

    // 二：处理加减法(不含其他特殊符号)
    static class AdditionAndSubtraction {
        int calculate(String s) {
            Stack<Integer> stack = new Stack<>();
            // 记录算式中的数字
            int num = 0;
            // 记录num前的符号，初始化为+；
            char sign = '+';
            for (int i = 0; i < s.length(); i++) {
                char c = s.charAt(i);
                // 如果是数字，连续读取到num中
                if (Character.isDigit(c)) {
                    num = num * 10 + (c - '0');
                }
                // 如果不是数字，就是遇到下一个符号，或者是算式的末尾
                // 那么之前的数字和符号就要存进栈中
                // 另外注意，不只是遇到新的符号会触发入栈，当 i 走到了算式的尽头（i == s.size() - 1 ），也应该将前面的数字入栈，方便后续计算最终结果。
                if (c == '+' || c == '-' || i == s.length() - 1) {
                    switch (sign) {
                        case '+':
                            stack.push(num);
                            break;
                        case '-':
                            stack.push(-num);
                            break;
                    }
                    // 更新符号为当前符号，数字清零
                    sign = c;
                    num = 0;
                }
            }
            int res = 0;
            while (!stack.isEmpty()) {
                res += stack.pop();
            }
            return res;
        }

        public static void main(String[] args) {
            new AdditionAndSubtraction().calculate("1-12+3");
        }
    }

    // 三：处理乘除法
    static class MultiAndDivision {
        public int calculate(String s) {
            Stack<Integer> stack = new Stack<>();
            // 记录算式中的数字
            int num = 0;
            // 记录num前的符号，初始化为+
            char sign = '+';
            for (int i = 0; i < s.length(); i++) {
                char c = s.charAt(i);
                if (Character.isDigit(c)) {
                    num = 10 * num + (c - '0');
                }
                if (c == '+' || c == '-' || c == '/' || c == '*' || i == s.length() - 1) {
                    int pre;
                    switch (sign) {
                        case '+':
                            stack.push(num);
                            break;
                        case '-':
                            stack.push(-num);
                            break;
                        // 只要拿出前一个数字做对应运算即可
                        case '*':
                            pre = stack.pop();
                            stack.push(pre * num);
                            break;
                        case '/':
                            pre = stack.pop();
                            stack.push(pre / num);
                            break;
                    }
                    // 更新符号为当前符号，数字清零
                    sign = c;
                    num = 0;
                }
            }
            // 将栈中所有结果求和就是答案
            int res = 0;
            while (!stack.isEmpty()) {
                res += stack.pop();
            }
            return res;
        }

        // 方法二
        public int calculate1(String s) {
            int n = s.length();
            Deque<Integer> stack = new ArrayDeque<>();
            int num = 0;
            char sign = '+';
            for (int i = 0; i < n; i++) {
                char c = s.charAt(i);
                if (Character.isDigit(c)) {
                    /*整体上，这个表达式就是不断地将新读取的数字字符整合到正在构建的整数值中。
                    每次读取一个数字字符，都通过这个表达式更新 num 的值，直到处理完整个数字字符串。*/
                    num = num * 10 + (c - '0');
                }
                // Character.isDigit(c)：判断是否为数字，Character.isWhitespace(c)判断是否为空格
                if ((!Character.isDigit(c) && !Character.isWhitespace(c)) || i == n - 1) {
                    // 这里的sign实际就是上一次的sign值，所以stack push时，取决于上一次的sign值
                    if (sign == '-') {
                        stack.push(-num);
                    } else if (sign == '+') {
                        stack.push(num);
                    } else if (sign == '*') {
                        stack.push(stack.pop() * num);
                    } else if (sign == '/') {
                        stack.push(stack.pop() / num);
                    }
                    sign = c; // 记录上一次的符号，为后续的sign判断做准备
                    num = 0;
                }
            }
            int res = 0;
            while (!stack.isEmpty()) {
                res += stack.pop();
            }
            return res;
        }
    }

    // 四：处理括号
    static class Brackets {
        // 将上面的代码嵌套了一层
        // 这里我们定义了一个新的函数 _calculate，
        // 它接受三个参数，分别是字符串 s，以及字符串的左右边界 start 和 end。这样我们就可以计算 s 中任意一个子表达式的值了。
        // 那么，为什么说处理括号没有看起来那么难呢，因为括号具有递归性质。我们拿字符串 3*(4-5/2)-6 举例：
        // calculate(3 * (4 - 5/2) - 6)
        //= 3 * calculate(4 - 5/2) - 6
        //= 3 * 2 - 6
        //= 0

        // 可以脑补一下，无论多少层括号嵌套，通过 _calculate 函数递归调用自己，都可以将括号中的算式算出结果。
        // 换句话说，括号包含的算式，我们直接视为一个数字就行了。
        // 那么现在的问题是，如果我遇到一个左括号 (，我怎么知道这个括号对应的右括号 ) 在哪里呢？
        // 这就又要用到栈了，我们可以对 s 进行预计算，提前找出每个左括号对应的右括号的位置。
        int calculate(String s) {
            return _calculate(s, 0, s.length() - 1);
        }

        // 定义：返回 s[start..end] 内的表达式的计算结果
        int _calculate(String s, int start, int end) {
            // 需要把字符串转成双端队列方便操作
            Stack<Integer> stk = new Stack<>();
            // 记录算式中的数字
            int num = 0;
            // 记录 num 前的符号，初始化为 +
            char sign = '+';
            for (int i = start; i <= end; i++) {
                char c = s.charAt(i);
                if (Character.isDigit(c)) {
                    num = 10 * num + (c - '0');
                }

                if (c == '+' || c == '-' || c == '/' || c == '*' || i == s.length() - 1) {
                    int pre;
                    switch (sign) {
                        case '+':
                            stk.push(num);
                            break;
                        case '-':
                            stk.push(-num);
                            break;
                        // 只要拿出前一个数字做对应运算即可
                        case '*':
                            pre = stk.pop();
                            stk.push(pre * num);
                            break;
                        case '/':
                            pre = stk.pop();
                            stk.push(pre / num);
                            break;
                    }
                    // 更新符号为当前符号，数字清零
                    sign = c;
                    num = 0;
                }
            }
            // 将栈中所有结果求和就是答案
            int res = 0;
            while (!stk.isEmpty()) {
                res += stk.pop();
            }
            return res;
        }

        // 依据上述的结论，得出下面代码
        public int calculate1(String s) {
            // key是左括号的索引，value是对应右括号的索引
            Map<Integer, Integer> rightIndex = new HashMap<>();
            // 利用栈结构来找到对应的括号
            Stack<Integer> stack = new Stack<>();
            for (int i = 0; i < s.length(); i++) {
                if (s.charAt(i) == '(') {
                    stack.push(i);
                } else if (s.charAt(i) == ')') {
                    rightIndex.put(stack.pop(), i);
                }
            }
            return _calculate(s, 0, s.length() - 1, rightIndex);
        }

        // 定义：返回 s[start..end] 内的表达式的计算结果
        public int _calculate(String s, int start, int end, Map<Integer, Integer> rightIndex) {
            // 需要把字符转成双端队列方便操作
            Deque<Integer> stack = new LinkedList<>();
            // 记录算式中的数字
            int num = 0;
            // 记录num前的符号，初始化为+
            char sign = '+';
            for (int i = start; i <= end; i++) {
                char c = s.charAt(i);
                if (Character.isDigit(c)) {
                    num = 10 * num + (c - '0');
                }
                if (c == '(') {
                    // 递归计算括号内的表达式
                    num = _calculate(s, i + 1, rightIndex.get(i) - 1, rightIndex);
                    i = rightIndex.get(i);
                }
                if (c == '+' || c == '-' || c == '*' || c == '/' || i == end) {
                    int pre;
                    switch (sign) {
                        case '+':
                            stack.push(num);
                            break;
                        case '-':
                            stack.push(-num);
                            break;
                        case '*':
                            pre = stack.pop();
                            stack.push(pre * num);
                            break;
                        case '/':
                            pre = stack.pop();
                            stack.push(pre / num);
                            break;
                    }
                    // 更新符号为当前符号，数字清零
                    sign = c;
                    num = 0;
                }
            }
            int res = 0;
            while (!stack.isEmpty()) {
                res += stack.pop();
            }
            return res;
        }

        // 这里不包括乘除运算
        public int calculate2(String s) {
            Deque<Integer> stack = new ArrayDeque<>();
            int sign = 1; // 这里的1表示正数，-1表示负数
            int result = 0; // 返回的结果
            int num = 0; // 连续多次完整的数字组合
            for (int i = 0; i < s.length(); i++) {
                char c = s.charAt(i);
                // + - 都是实时计算的
                if (Character.isDigit(c)) {
                    num = num * 10 + (c - '0');
                } else if (c == '+') {
                    result += sign * num;
                    num = 0;
                    sign = 1;
                } else if (c == '-') {
                    result += sign * num;
                    num = 0;
                    sign = -1;
                } else if (c == '(') {
                    stack.push(result);
                    stack.push(sign);
                    result = 0;
                    sign = 1;
                } else if (c == ')') {
                    // 因为都是实时计算，所以即使在括号中也就存放两个值
                    result += sign * num; // 实时计算的，先将当前的数字num和当前符号相乘，并累加到结果result中
                    num = 0;
                    // 从栈中弹出上一个符号和上一个结果
                    int prevSign = stack.pop(); // 因为存放的顺序是优先存在result，然后存放符号，所以优先取符号
                    int prevResult = stack.pop();
                    result = prevResult + prevSign * result;
                }
            }
            return result + sign * num;
        }

        public static void main(String[] args) {
            new Brackets().calculate1("3*(4-5/2)-6");
        }
    }

    // 224. 基本计算器（+-()）
    // 给你一个字符串表达式 s ，请你实现一个基本计算器来计算并返回它的值。
    // 注意:不允许使用任何将字符串作为数学表达式计算的内置函数，比如 eval() 。
    static class Calculate {
        // 乘除法优先于加减法体现在，乘除法可以和栈顶的数结合，而加减法只能把自己放入栈。
        public int calculate(String s) {
            Deque<Integer> stack = new ArrayDeque<>();
            int sign = 1; // 这里的1表示正数，-1表示负数
            int result = 0; // 返回的结果
            int num = 0; // 连续多次完整的数字组合
            for (int i = 0; i < s.length(); i++) {
                char c = s.charAt(i);
                // + - 都是实时计算的
                if (Character.isDigit(c)) {
                    num = num * 10 + (c - '0');
                } else if (c == '+') {
                    result += sign * num;
                    num = 0;
                    sign = 1;
                } else if (c == '-') {
                    result += sign * num;
                    num = 0;
                    sign = -1;
                } else if (c == '(') {
                    stack.push(result);
                    stack.push(sign);
                    result = 0;
                    sign = 1;
                } else if (c == ')') {
                    // 因为都是实时计算，所以及时在括号中也就存放两个值
                    result += sign * num; // 实时计算的，现将当前的数字num和当前符号相乘，并累加到结果result中
                    num = 0;
                    // 从栈中弹出上一个符号和上一个结果
                    int preSign = stack.pop(); // 因为存放的顺序是优先存在result，然后存放符号，所以优先取符号
                    int prevResult = stack.pop();
                    result = prevResult + preSign * result;
                }
            }
            return result + sign * num;
        }
    }

    // 71. 简化路径
    // 给你一个字符串 path ，表示指向某一文件或目录的 Unix 风格 绝对路径 （以 '/' 开头），请你将其转化为 更加简洁的规范路径。
    //在 Unix 风格的文件系统中规则如下：
    //一个点 '.' 表示当前目录本身。
    //此外，两个点 '..' 表示将目录切换到上一级（指向父目录）。
    //任意多个连续的斜杠（即，'//' 或 '///'）都被视为单个斜杠 '/'。
    //任何其他格式的点（例如，'...' 或 '....'）均被视为有效的文件/目录名称。
    //返回的 简化路径 必须遵循下述格式：
    //始终以斜杠 '/' 开头。
    //两个目录名之间必须只有一个斜杠 '/' 。
    //最后一个目录名（如果存在）不能 以 '/' 结尾。
    //此外，路径仅包含从根目录到目标文件或目录的路径上的目录（即，不含 '.' 或 '..'）。
    //返回简化后得到的 规范路径 。
    //示例 1：
    //输入：path = "/home/"
    //输出："/home"
    //解释：
    //应删除尾随斜杠。
    //示例 2：
    //输入：path = "/home//foo/"
    //输出："/home/foo"
    //解释：
    //多个连续的斜杠被单个斜杠替换。
    //示例 3：
    //输入：path = "/home/user/Documents/../Pictures"
    //输出："/home/user/Pictures"
    //解释：
    //两个点 ".." 表示上一级目录（父目录）。
    //示例 4：
    //输入：path = "/../"
    //输出："/"
    //解释：
    //不可能从根目录上升一级目录。
    //示例 5：
    //输入：path = "/.../a/../b/c/../d/./"
    //输出："/.../b/d"
    //解释：
    //"..." 在这个问题中是一个合法的目录名。
    static class SimplifyPath {
        public String simplifyPath(String path) {
            List<String> stk = new ArrayList<>();
            for (String s : path.split("/")) {
                if (s.isEmpty() || s.equals(".")) {
                    continue;
                }
                if (!s.equals("..")) {
                    stk.add(s);
                } else if (!stk.isEmpty()) { // 这里的意思是返回上一层
                    stk.remove(stk.size() - 1);
                }
            }
            // String.join("/", stk) 是 Java 中用于字符串拼接的方法，
            // 其作用是将集合（如 List、数组等）中的元素用指定的分隔符（这里是 /）连接成一个字符串
            return "/" + String.join("/", stk);
        }
    }
}
